package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月26日
*时间：上午11:18:13
*/
public class Q7 {

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            return null;
        }
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        boolean isFirst = true;
        boolean hasChild = true;
        while (hasChild) {
            hasChild = false;
            List<TreeNode> list2 = new ArrayList<>();
            for (TreeNode t : list) {
                String code;
                if (t == null) {
                    code = "#";
                    list2.add(null);
                    list2.add(null);
                } else {
                    code = String.valueOf(t.val);
                    if (t.left != null || t.right != null) {
                        hasChild = true;
                    }
                    list2.add(t.left);
                    list2.add(t.right);
                }
                if (isFirst) {
                    sb.append(code);
                    isFirst = false;
                } else {
                    sb.append(",").append(code);
                }
            }
            list = new ArrayList<>(list2);
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == null || data.length() <= 0) {
            return null;
        }
        String[] split = data.split(",");
        List<TreeNode> list = new ArrayList<>();
        TreeNode node = new TreeNode(Integer.parseInt(split[0]));
        list.add(node);
        int i = 1;
        a: while (i < split.length) {
            List<TreeNode> list2 = new ArrayList<>();
            for (TreeNode t : list) {
                if (t == null) {
                    list2.add(null);
                    list2.add(null);
                    i += 2;
                } else {
                    t.left = getTreeNode(split[i++]);
                    list2.add(t.left);
                    if (i < split.length) {
                        t.right = getTreeNode(split[i++]);
                        list2.add(t.right);
                    } else {
                        break a;
                    }

                }
                if (i >= split.length) {
                    break a;
                }

            }
            list = new ArrayList<>(list2);
        }
        return node;
    }

    private TreeNode getTreeNode(String s) {
        if (s == null || s.equals("#")) {
            return null;
        }
        return new TreeNode(Integer.parseInt(s));
    }

    @Test
    public void testA() {
        TreeNode node = new TreeNode(0);
        TreeNode n11 = new TreeNode(11);
        TreeNode n12 = new TreeNode(12);
        TreeNode n21 = new TreeNode(21);
        TreeNode n22 = new TreeNode(22);
        TreeNode n31 = new TreeNode(31);
        TreeNode n33 = new TreeNode(33);
        TreeNode n34 = new TreeNode(34);
        node.left = n11;
        node.right = n12;
        n11.left = n21;
        n11.right = n22;
        n21.left = n31;
        n22.left = n33;
        n22.right = n34;
        String s = serialize(node);
        System.out.println(s);
        TreeNode t = deserialize(s);
        System.out.println(t);

    }
}
